package LeetCode.LC80;

/**
 * 移位解法
 * 超时
 * 复杂度分析
 *
 *     时间复杂度：让我们看看最耗时的操作是什么：
 *         我们必须遍历数组中的所有元素，若数组中有 N 个元素，则花费的时间为 O(N)。
 *         删除多余的重复项，del 操作也是 O(N)。
 *         最糟糕的情况是数组中的元素都相同，则我们需要执行 N−1 次的删除操作，则需要花费 O(N^2)。
 *         总的复杂度：O(N)+O(N^2)≡O(N^2)
 *
 *     空间复杂度：O(1)，我们在原地修改数组。
 *
 * @author corn
 * @create 2020-11-06-9:42
 */
public class Solution2 {
    public int removeDuplicates(int[] nums) {
        //每当删除一个字符时，length自动减一，最后length就是剩下的数组长度
        int length = nums.length;
        //num：记录当前字符，count记录当前字符出现的次数
        int num = nums[0];
        int count = 1;
        //逐一判断
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == num){
                if(count == 2){
                    //同一字符出现第三次，删除该字符，length减一，i返回一步（删除字符时，后续的全部向前移动一位）
                    del(nums, i);
                    length--;
                    i--;
                }else{
                    count ++;
                }
            }else{
                //新字符出现，重新开始记录
                num = nums[i];
                count = 1;
            }
        }
        return length;
    }
    public void del(int[] nums, int index){
        for(int i = index + 1; i < nums.length; i++){
            nums[i - 1] = nums[i];
        }
    }
}
